package pers.qianyu.month_202012.date_20201219.shuffle;

import org.junit.*;

import java.util.*;
import java.util.stream.*;

/**
 * 洗牌算法
 *
 * @author mizzle rain
 * @date 2020-12-19 15:18
 */
public class Shuffle {
    public void shuffle(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            // 生成一个 [i, len - 1] 之间的随机整数
            int r = ((int) (Math.random() * (len - i)) + i);
            swap(nums, i, r);
        }
    }

    // 注意：异或交换法，要保证 i 不等于 j ，所以这里不能用
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    // 蒙特卡罗方法验证正确性
    @Test
    public void test1() {
        int[] arr = {1, 2, 3};
        Map<String, Integer> map = Stream.of("123", "132", "213", "231", "312", "321")
                .collect(Collectors.toMap(i -> i, i -> 0));
        for (int i = 0; i < 100_000; i++) {
            new Shuffle().shuffle(arr);
            String s = Arrays.stream(arr).boxed()
                    .map(String::valueOf)
                    .collect(Collectors.joining(""));
            map.put(s, map.get(s) + 1);
        }
        map.forEach((k, v) -> System.out.println(k + ": " + v));
    }
}
